/**
 * 给你一个 下标从 0 开始 的正整数数组w ，其中w[i] 代表第 i 个下标的权重。
 *
 * 请你实现一个函数pickIndex，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i的 概率 为 w[i] / sum(w) 。
 *
 * 例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3)= 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3)= 0.75（即，75%）。
 *
 *
 * 链接：https://leetcode.cn/problems/random-pick-with-weight
 * 思路：前缀和加二分查找
 * 题解：https://labuladong.gitee.io/algo/2/20/30/
 * 假设给你输入的权重数组是 w = [1,3,2,1]，我们想让概率符合权重，那么可以抽象一下，根据权重画出这么一条彩色的线段：
 * 如果我在线段上面随机丢一个石子，石子落在哪个颜色上，我就选择该颜色对应的权重索引，那么每个索引被选中的概率是不是就是和权重相关联了？
 * 所以，你再仔细看看这条彩色的线段像什么？这不就是 前缀和数组 嘛：那么接下来，如何模拟在线段上扔石子？
 *
 * 当然是随机数，比如上述前缀和数组 preSum，取值范围是 [1, 7]，那么我生成一个在这个区间的随机数 target = 5，就好像在这条线段中随机扔了一颗石子：
 * preSum{0,1,4,6,7}
 * 比如说，值为1就是w中下标为0的概率；值为2,3,4就是w中下标为1的概率，值为5,6就是w中下标为2的概率，值为7就是w下标为3的概率
 * 也就是说w中数字为多少，在preSum中就是有多少个数字，这样就是概率了
 */
class PickIndex {
    int[] pre;
    int total;
    
    public PickIndex(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 1; i < w.length; ++i) {
            pre[i] = pre[i - 1] + w[i];
        }
        total = Arrays.stream(w).sum();
    }
    
    public int pickIndex() {
        int x = (int) (Math.random() * total) + 1;
        return binarySearch(x);
    }

    private int binarySearch(int x) {
        int low = 0, high = pre.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (pre[mid] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

